package Algorithms;

import java.util.Random;
import java.util.Scanner;

public class QuickSort {
	public QuickSort(Comparable[] a) {
		sort(a, 0, a.length-1);
	}
	private static void sort(Comparable[] a,int lo,int hi) {
		if(hi<=lo) return;
			int j=partition(a,lo,hi);
			sort(a, lo, j-1);
			sort(a, j+1, hi);
	}
	private static int partition(Comparable[]a,int lo,int hi) {
		int i=lo;int j=hi+1;
		Comparable v=a[lo];
		while(true) {
			while(less(a[++i],v)) if(i==hi)break;
			while(less(v, a[--j])) if(j==lo)break;
			if(i>=j)break;
			exch(a, i, j);
		}
		exch(a, lo, j);
		return j;
	}
	private static void exch(Comparable[]a,int i,int min) {
		Comparable t=a[i];a[i]=a[min];a[min]=t;
	} 
	private static boolean less(Comparable v,Comparable w) {
		return v.compareTo(w)<0;
	}
	
	
	
	public static void show(Comparable[] a) {
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println("");
	}
	public static void main(String[]args) {
		Scanner scanner=new Scanner(System.in);
		String[]a=new String[10];
		for(int i=0;i<10;i++) {
			a[i]=scanner.next();
		}
		show(a);
		sort(a,0,a.length-1);
		show(a);
	}
}
